namespace PF {
    export class Util {
        /**根据父记录回溯并返回路径。
        （包括起始节点和结束节点） */
        static backtrace(node: Node) {
            var path = [[node.x, node.y]];
            while (node.parent) {
                node = node.parent;
                path.push([node.x, node.y]);
            }
            return path.reverse();
        }

        /**
            从起始节点和结束节点回溯，并返回路径。
            （包括起始节点和结束节点） */
        static biBacktrace(nodeA: Node, nodeB: Node) {
            var pathA = this.backtrace(nodeA),
                pathB = this.backtrace(nodeB);
            return pathA.concat(pathB.reverse());
        }

        /**
         * 计算路径的长度。
         */
        static pathLength(path:Array<Array<number>>) {
            var i, sum = 0, a, b, dx, dy;
            for (i = 1; i < path.length; ++i) {
                a = path[i - 1];
                b = path[i];
                dx = a[0] - b[0];
                dy = a[1] - b[1];
                sum += Math.sqrt(dx * dx + dy * dy);
            }
            return sum;
        }

        /**给定压缩路径，返回包含所有段的新路径
            在它的插值。 */
        static expandPath(path:Array<Array<number>>) {
            var expanded = [],
                len = path.length,
                coord0, coord1,
                interpolated,
                interpolatedLen,
                i, j;
        
            if (len < 2) {
                return expanded;
            }
        
            for (i = 0; i < len - 1; ++i) {
                coord0 = path[i];
                coord1 = path[i + 1];
        
                interpolated = this.interpolate(coord0[0], coord0[1], coord1[0], coord1[1]);
                interpolatedLen = interpolated.length;
                for (j = 0; j < interpolatedLen - 1; ++j) {
                    expanded.push(interpolated[j]);
                }
            }
            expanded.push(path[len - 1]);
        
            return expanded;
        }

        /**给定起始坐标和结束坐标，返回所有坐标
            在这些坐标形成的直线上，基于Bresenham算法。 */
        static interpolate(x0:number, y0:number, x1:number, y1:number) {
            var abs = Math.abs,
                line = [],
                sx, sy, dx, dy, err, e2;
        
            dx = abs(x1 - x0);
            dy = abs(y1 - y0);
        
            sx = (x0 < x1) ? 1 : -1;
            sy = (y0 < y1) ? 1 : -1;
        
            err = dx - dy;
        
            while (true) {
                line.push([x0, y0]);
        
                if (x0 === x1 && y0 === y1) {
                    break;
                }
                
                e2 = 2 * err;
                if (e2 > -dy) {
                    err = err - dy;
                    x0 = x0 + sx;
                }
                if (e2 < dx) {
                    err = err + dx;
                    y0 = y0 + sy;
                }
            }
        
            return line;
        }
    }
}